#include "MyBinaryTree.hpp"
template <typename Comparable>
class MyAvlTree
{
private:
    /*表示非平衡长度的静态常量*/
    static const int ALLOWED_IMBALANCE = 1;
    struct AvlNode
    {
        Comparable element;
        AvlNode *left;
        AvlNode *right;
        int height;
        /*左值初始化*/
        AvlNode (const Comparable & ele, AvlNode *lt, AvlNode *rt, int h = 0) : element {ele} , left {lt}, right {rt}, height {h} {}
        /*右值初始化*/
        AvlNode ( Comparable && ele , AvlNode * lt, AvlNode *rt , int h = 0 ) : element { std::move {ele} }, left {lt}, right {rt}, height{h} {}
    };

    /*内部方法*/
    /*插入节点*/
    void insert (const Comparable & x, AvlNode *& t)
    {
        /*插入*/
        if(t == nullptr)
            t = new AvlNode {x, nullptr, nullptr};
        /*递归查找*/
        else if (x < t->element)
            insert(x,t->left); 
        else if (t->element < x)
            insert(x,t->right);
        /*比二叉树多了一个平衡过程*/
        balance(t);
    }
    /*平衡节点*/
    void balance(AvlNode *& t)
    {
        if (t==nullptr)
            return;
        /*左右子树的高度差不能高于1*/
        if (height(h->left) - height(h->right) > ALLOWED_IMBALANCE)
            /*否则进行单旋转或双旋转*/
            if(height( t->left->left ) >= height(t->left->right) )
                rotateWithLeftChild(t);
            else
                doubleWithLeftChild(t);
        else if( height(t->right - height(t->left) > ALLOWED_IMBALANCE) )
            if (height(t->right->right) >= height(t->right->left) )
                rotateWithRightChild(t);
            else
                doubleWithLeftChild(t);
        
        t->height = max(height(t->left), height(t->right)) + 1;
    }
    /* 用左儿子k1旋转二叉树（此时k2为旧根，k1为新根）
     * 单旋转
     * 最后设置新根时考虑父根，只需把k2的位置用k1取代即可
     * 而一开始设置子节点时，k2的位置无影响
    */
    void rotateWithLeftChild(AvlNode *& k2)
    {
        AvlNode k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2->height = max(height(k2->left), height(k2->right)) + 1;
        k1->height = max(height(k1->left), k2->height) + 1; //k2->height就是k1->left->height
        k2 = k1;
    }
    /* 左-右双旋转（此时k3为旧根，k1为左子，k2为左右孙）
     * 更新高度，设置k2为新根，k1为左子，k3为右子
     * 
    */
    void doubleWithLeftChild (AvlNode *& k3)
    {
        rotateWithRightChild(k3->left);
        rotateWithLeftChild(k3);
    }
    /* 用右儿子k2旋转二叉树（此时k1为旧根，k2为新根）
     * 单旋转
     * 最后设置新根时考虑父根，只需把k1的位置用k2取代即可
     * 而一开始设置子节点时，k1的位置无影响
    */
    void rotateWithRightChild(AvlNode *& k1)
    {
        /*先让k1下降，并赋节点*/
        AvlNode k2 = k1->right;
        k1->right = k1->right->left;
        /*再让k2上升，连接k1*/
        k2->left = k1;
        /*再改变高度数据*/
        k1->height = max( height(k1->left), height(k1->right) ) + 1;
        k2->height = max( height(k2->left), k1->height ) + 1;
        /*设置新根*/
        k1 = k2;
    }
    /* 右-左双旋转（此时k3为旧根，k1为右子，k2为右左孙）
     * 更新高度，设置k2为新根，k3为左子，k1为右子
    */
    void doubleWithRightChild (AvlNode *& k3)
    {
        rotateWithLeftChild(k3->right);
        rotateWithRightChild(k3);
    }
    /*删除节点
     * x是被删除的项
     * t是子树根节点
    */
    void remove(const Comparable & x, AvlNode *& t)
    {
        /*空节点无需删除*/
        if (t==nullptr)
            return;
        /*递归查找*/
        if(x < t->element)
            remove(x, t->left);
        else if (t->element < x)
            remove(x, t->right);
        /*找到，但有两个子节点*/
        else if (t->left != nullptr && t->right != nullptr)
        {
            t->element -= findMin(t->right)->element;
            remove(t->element, t->right);
        }
        /*找到，且最多只有一个子节点*/
        else
        {   AvlNode *oldNode = t;
            t = (t->left != nullptr) ? t->left : t->right;
            delete oldNode;
        }
        balance(t);
    }

public:
    int height(AvlNode *t) const { return t == nullptr ? -1 : t->height; }
};